import java.util.*;

class Solution {
    
    /**
     * 删除数组中的重复项，使得数组中最多同时存在2个重复项
     * 用后面的重复项覆盖当前的重复项，但是在覆盖的时候始终保持最前面俩个数据不覆盖
     * 依次往后遍历，就可以保证数组中最多只有2个重复项
     * 1 1 1 1  2 2  3 3 3 3 3 3
     * 1 1 2 2  2 2  3 3 3 3 3 3
     * 1 1 2 2  3 3  3 3 3 3 3 3
     */
    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if (length <= 2) {
            return length;
        }
        int slow = 2, fast = 2;
        while (fast < length) {
            if (nums[slow - 2] != nums[fast]) {//找到下一个重复项
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
    
    /**
     * 合并俩个有序数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] ret = new int[m + n];
        int p1 = 0;
        int p2 = 0;
        int cur = 0;
        while (p1 < m || p2 < n) {
            if (p1 == m) {//数组一已放完
                cur = nums2[p2++];
            } else if (p2 == n) {//数组二已放完
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {//数组一中较小，放入结果集
                cur = nums1[p1++];
            } else {//数组二较小，放入结果集
                cur = nums2[p2++];
            }
            ret[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = ret[i];
        }
    }
    
    /**
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int n : nums) {//存入集合
            list.add(n);
        }
        for (int i = 0; i < k; i++) {//轮换
            Integer last = list.pollLast();
            list.addFirst(last);
        }
        for (int i = 0; i < nums.length; i++) {//返回原数组
            nums[i] = list.get(i);
        }
//        int n = nums.length;
//        int[] newArr = new int[n];
//        for (int i = 0; i < n; ++i) {
//            newArr[(i + k) % n] = nums[i];
//        }
//        System.arraycopy(newArr, 0, nums, 0, n);
    
    }
    
    /**
     * 使用哈希表统计数组中每个元素出现的次数
     *
     * @param nums
     * @return
     */
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {//如果map中没有这个num，就放入，并且计数1
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);//如果map中有这个num，就让count++
            }
        }
        return counts;
    }
    
    /**
     * 买卖股票的最佳时机
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int pMin = prices[0];
        int pMax = prices[0];
        int tempRet = 0;
        int ret = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < pMin) {//找到购入股票的时间点，同时刷新初始值
                pMin = prices[i];
                pMax = prices[i];
            }
            if (prices[i] > pMax) {//计算利润
                pMax = prices[i];
                tempRet = pMax - pMin;//当前利润
                if (tempRet > ret) {//当前利润大于历史利润就更新
                    ret = tempRet;
                }
            }
        }
        return ret;
    }
    
    /**
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     *
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {//当前股票处于上升趋势
                int temp = prices[i] - prices[i - 1];//相比昨天赚了多少
                sum += temp;//每天只要能赚钱就卖股票
            }
        }
        return sum;
    }
    
    /**
     * 跳跃游戏
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false
     * [2,3,1,1,4]
     * [3,2,1,0,4]
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int fast = 0;//当前能跳的最远举例
        for (int i = 0; i < nums.length; i++) {
            if (fast < i) {
                return false;
            }
            fast = Math.max(fast, i + nums[i]);
        }
        return true;
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums1 int整型ArrayList
     * @param nums2 int整型ArrayList
     * @return int整型ArrayList
     */
    public ArrayList<Integer> intersection(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
        // write code here
        ArrayList<Integer> ret = new ArrayList<>();
        int a = 0;//遍历nums1的指针
        while (a < nums1.size()) {
            Integer tempA = nums1.get(a);//取出nums1中的值
            for (int tempB : nums2) {//遍历nums2,挨个与tempA对比
                if (tempA.equals(tempB) && !ret.contains(tempA)) {//如果tempA和tempB相等并且该元素在ret中不存在
                    ret.add(tempA);//如果tempA和tempB相等并且该元素在ret中不存在则加入
                }
            }
            a++;
        }
        return ret;
    }
    
    
}
    



